﻿using System;
using System.Collections.Generic;
using System.Linq;
using Algoritmia.StateSpaces;
using Algoritmia.Schemes;
using Algoritmia.Utils;
using Lists = Algoritmia.DataStructures.Lists;


namespace Algoritmia.Problems.SubsetSum
{
    public class SubsetSumStateSpace1 : IReversibleForwardStateSpace<Lists.IList<int>,int>
    {
        private readonly Func<IEnumerable<int>,Lists.IList<int>> _createList;
        private readonly Lists.IList<int> _w;
        private readonly int _W;
        private readonly int _n;

        public SubsetSumStateSpace1(IEnumerable<int> w,int W, Func<IEnumerable<int>,Lists.IList<int>> createList = null )
        {
            _createList = createList ?? (it => AlgoritmiaFactory.Lists<int>.BuildDefault(it));
            _w = _createList(w);
            _W = W;
            _n = _w.Count;
        }

        public Lists.IList<int> Decide(Lists.IList<int> state, int decision)
        {
            state.Add(decision);
            return state;
        }

        public IEnumerable<int> Decisions(Lists.IList<int> state)
        {
            if (state.Count < _n)
            {
                yield return 0;

                int weight = (from i in Enumerable.Range(0, state.Count)
                              select state[i]*_w[i]).Sum();
                    
                if (weight + _w[state.Count] <= _W)
                {
                    yield return 1;
                }
            }

        }

        public IEnumerable<Lists.IList<int>> InitialStates
        {
            get { yield return _createList(Enumerable.Empty<int>()); }
        }

        public bool IsFinal(Lists.IList<int> state)
        {
            return state.Count == _n && (from i in Enumerable.Range(0, state.Count)
                                        select state[i]*_w[i]).Sum() == _W;
        }

        public Lists.IList<int> Undo(Lists.IList<int> state, int decision)
        {
            state.RemoveAt(state.Count - 1);
            return state;
        }
    }

    public class SubsetSumSolver1
    {
        private readonly BacktrackingEnumerator<Lists.IList<int>, int, Lists.IList<int>> _enumerator;

        public SubsetSumSolver1()
        {
            _enumerator =
                new BacktrackingEnumerator<Lists.IList<int>, int, Lists.IList<int>>(
                    (space, initial, decisions, final) => decisions);
        }

        public Lists.IList<int> Solve(IEnumerable<int> w, int W)
        {
            var space = new SubsetSumStateSpace1(w, W);
            return _enumerator.First(space);
        }
    }
}
